Large graph-based knowledge bases represent factual information about the world. For example, in a data graph, entities, such as people, places, phrases, words, classes, facts, things, concepts, etc., may be stored as nodes and the edges between nodes may indicate a relationship between the entities. The basic unit of such a data graph can be a triple that includes two nodes, or entities, and an edge label. The first node is sometimes referred the source or subject node, and the second node is sometimes referred to as the target or object node. Of course, a triple may include additional information, such as metadata about the entities and/or the relationship, in addition to identifying the subject, predicate, and object.
Users can define queries or collections for the graph. A collection or query defines constraints a node must satisfy to be a member of the set of nodes responsive to the query. The constraints usually specify what relationship(s) a node must have or not have to be a member of the query results, e.g., a member of the collection. Such queries (i.e., collections) are used extensively in search, data mining, ad targeting, recommendation systems, etc., and membership is often stored because calculating membership can be expensive in a large graph. But as nodes and relationships are added or deleted from the graph, the saved members can become stale, especially in large graphs that are frequently updated.